import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
* @description: 927. 三等分
* @author hewei
* @date 2022/10/6 14:24
* @version 1.0
*/

public class ThreeEqualParts {

    public static void main(String[] args) {
        int[] nums = {1,0,1,0,1};
        System.out.println(Arrays.toString(new ThreeEqualParts().threeEqualParts(nums)));
    }

    public int[] threeEqualParts1(int[] arr) {
        HashMap<String, List<Integer>> map = new HashMap<>();
        StringBuilder stringBuilder = new StringBuilder();
        int n = arr.length;
        for (int i = n - 1; i >= 0; i--) {
            stringBuilder.insert(0, arr[i]);
            String s = stringBuilder.toString();
            s = s.replaceFirst("^0*", "");
            if (!map.containsKey(s)) map.put(s, new ArrayList<>());
            map.get(s).add(i);
        }
        String s = stringBuilder.toString();
        for (int i = 0; i < n - 2; i++) {
            String temp = s.substring(0, i + 1);
            temp = temp.replaceFirst("^0*", "");
            List<Integer> list = map.get(temp);
            if (list == null || list.size() == 0) continue;
            for (Integer index : list) {
                if (index <= i) continue;
                String first = s.substring(i + 1, index).replaceFirst("^0*", "");
                if (first.equals(temp)) return new int[]{i, index};
            }
        }
        return new int[]{-1, -1};
    }

    public int[] threeEqualParts(int[] arr) {
        int count = 0;
        int n = arr.length;
        for (int k : arr) {
            if (k == 1) ++count;
        }
        if (count % 3 != 0) return new int[]{-1, -1};
        if (count == 0) return new int[]{0, 2};
        int p1 = -1;
        int p2 = -1;
        int p3 = -1;
        int target = count / 3;
        count = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == 1) {
                if (count == 0) {
                    if (p1 == -1) {
                        p1 = i;
                    } else if (p2 == -1) {
                        p2 = i;
                    } else p3 = i;
                }
                ++count;
            }
            if (count == target) count = 0;
        }
        int length = n - p3;
        if (p1 + length > p2 || p2 + length > p3) return new int[]{-1, -1};
        for (int i = 1; i < length; i++) {
            if (arr[p1 + i] != arr[p2 + i] || arr[p2 + i] != arr[p3 + i]) return new int[]{-1, -1};
        }
        return new int[]{p1 + length - 1, p2 + length};
    }
}